/*
*	ID : Pallab
* 	PROG : E
* 	LANG : C++
* 	2012-12-10-17.40.21 Monday
*
* 	"I have not failed, I have just found 10000 ways that won't work.
*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <fstream>
#include <string>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <numeric>
#include <stack>
#include <functional>
#include <bitset>
#include <iomanip>
#include <chrono>
#include <unordered_set>
#include <unordered_map>
#include <array>

#include <ctime>
#include <cassert>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <climits>
#include <cstring>
#include <cstdlib>

using namespace std;

#define foR(i1,st,ed) for(int i1 = st , j1 = ed ; i1 < j1 ; ++i1 )
#define fo(i1,ed) foR( i1 , 0 , ed )
#define foE(i1,st,ed) foR( i1, st, ed+1 )
#define foit(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); i++)
#define bip system("pause")
#define Int long long
#define pb push_back
#define SZ(X) (int)(X).size()
#define LN(X) (int)(X).length()
#define mk make_pair
#define SET( ARRAY , VALUE ) memset( ARRAY , VALUE , sizeof(ARRAY) )
#define line puts("")

inline void wait(double seconds) {
    double endtime = clock() + (seconds * CLOCKS_PER_SEC);
    while (clock() < endtime) {
        ;
    }
}
template<class T>
inline T fastIn() {
    register char c=0;
    register T a=0;
    bool neg=false;
    while(c<33)c=getchar();
    while(c>33) {
        if(c=='-') {
            neg=true;
        } else {
            a= (a*10)+(c-'0');
        }
        c=getchar();
    }
    return neg?-a:a;
}
const int mx_day=405;
struct node {
    int food_need,who;
    bool operator<(const node &r)const {
        return food_need<r.food_need;
    }
};
vector<node> food_need[mx_day];
int day_count,myneed;
int supply[mx_day];

inline void read() {
    day_count=fastIn<int>(),myneed=fastIn<int>();
    fo(i,day_count)supply[i]=fastIn<int>();


    int frm,to,frnd_cnt,need;
    frnd_cnt=fastIn<int>();
    fo(i,frnd_cnt) {
        frm=fastIn<int>()-1,to=fastIn<int>()-1,need=fastIn<int>();
        foE(j,frm,to) {
            food_need[j].pb(node {need,i+1});
        }
    }
    for(int i=0; i<day_count; ++i) {
        sort(food_need[i].begin(),food_need[i].end());
    }
}
struct state {
    bool f;
    int v;
};
state dp[mx_day][mx_day];
int go(int at, int carry) {
    if(at>=day_count)return 0;
    state &bst=dp[at][carry];

    if(bst.f)return bst.v;
    bst.f=true;
    bst.v=0;
    int cur_food=supply[at],cur_carry=carry,rating=0;

    if(cur_carry>=myneed) {
        cur_carry-=myneed;
    } else {
        cur_food=cur_food+cur_carry-myneed;
        cur_carry=0;
    }
    bst.v=max(bst.v, go(at+1,cur_food) );
for(auto &x:food_need[at]) {
        if( cur_food+cur_carry>=x.food_need ) {
            ++rating;
            if(cur_carry>=x.food_need) {
                cur_carry-=x.food_need;
            } else {
                cur_food=cur_food+cur_carry-x.food_need;
                cur_carry=0;
            }
            bst.v=max(bst.v,rating+go(at+1,cur_food));
        }
    }

    return bst.v;
}
int optimal_result;
vector<int> days[mx_day];
void bk(int at,int carry) {
    if(at>=day_count)return ;

    int cur_food=supply[at],cur_carry=carry,rating=0;

    if(cur_carry>=myneed) {
        cur_carry-=myneed;
    } else {
        cur_food=cur_food+cur_carry-myneed;
        cur_carry=0;
    }
    if(optimal_result==go(at+1,cur_food) ) {
        bk(at+1,cur_food);
        return ;
    }
for(auto &x:food_need[at]) {
        if( cur_food+cur_carry>=x.food_need ) {
            ++rating;
            if(cur_carry>=x.food_need) {
                cur_carry-=x.food_need;
            } else {
                cur_food=cur_food+cur_carry-x.food_need;
                cur_carry=0;
            }
            days[at].pb(x.who);
            if( optimal_result==rating+go(at+1,cur_food)) {
                optimal_result-=rating;
                bk(at+1,cur_food);
                return ;
            }
        }
    }

}
inline void proc() {
    SET(dp,false);
    int retval=go(0,0);
    cout<<retval<<'\n';
    optimal_result=retval;
    bk(0,0);
    fo(i,day_count) {
        cout<<SZ(days[i]);
for(auto&ppl:days[i])cout<<' '<<ppl;
        line;
    }
}
int main() {
    int kase = 1;
#if defined( xerxes_pc )
    if (!freopen("in1", "r", stdin))
        puts("error opening file in "), assert(0);
    kase = 1;
#else
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#endif
    fo(i,kase) {
        read();
        proc();
    }
    return 0;
}
